package com.zl.learning.arithmetic.leetcode;

/**
 * 给定两个非空链表来表示两个非负整数。位数按照逆序方式存储，它们的每个节点只存储单个数字。将两数相加返回一个新的链表。
 * <p>
 * 你可以假设除了数字 0 之外，这两个数字都不会以零开头。
 * <p>
 * 示例：
 * <p>
 * 输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
 * 输出：7 -> 0 -> 8
 * 原因：342 + 465 = 807
 */
public class AddTwoNumbers {
    public static void main(String[] args) {
        AddTwoNumbers solution = new AddTwoNumbers();
        ListNode l1 = ListNode.builder(2, 4, 3, 8);
        ListNode l2 = ListNode.builder(5, 6, 4, 4);

        ListNode l3 = solution.addTwoNumbers(l1, l2);
//        print(l3);
        while (l3 != null) {
            System.out.println(l3.val);
            l3 = l3.next;
        }
    }

    private static void print(ListNode node) {
        if (node != null) {
            System.out.print(node.val + " ");
            print(node.next);
        }
    }

    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode dummyHead = new ListNode(0);
        ListNode p = l1, q = l2, curr = dummyHead;
        int carry = 0;
        while (p != null || q != null) {
            int x = (p != null) ? p.val : 0;
            int y = (q != null) ? q.val : 0;
            int sum = carry + x + y;
            carry = sum / 10;
            curr.next = new ListNode(sum % 10);
            curr = curr.next;
            if (p != null) p = p.next;
            if (q != null) q = q.next;
        }
        if (carry > 0) {
            curr.next = new ListNode(carry);
        }
        return dummyHead.next;
    }

    public static class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
        }

        static ListNode builder(int... vals) {
            ListNode l1 = new ListNode(vals[0]);
//            build(l1, 1, vals);
            ListNode curr = l1;
            for (int i = 1; i < vals.length; i++) {
                ListNode l2 = new ListNode(vals[i]);
                curr.next = l2;
                curr = l2;
            }
            return l1;
        }

        private static void build(ListNode l1, int index, int... vals) {
            if (index < vals.length) {
                ListNode l2 = new ListNode(vals[index]);
                l1.next = l2;
                index++;
                build(l2, index, vals);
            }
        }
    }
}
